from BuildTree import *


class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """

        def build(node: TreeNode):
            if not node: return None
            left = build(node.left)
            right = build(node.right)
            node.right = left
            p = node
            while p.right:
                p = p.right
            p.right = right
            node.left = None
            return node

        build(root)
        ...


if __name__ == '__main__':
    s = Solution()
    null = None
    root = build_tree_from_level_order([1, 2, 5, 3, 4, null, 6])
    s.flatten(root)
